package com.wu.leetcode.sort.heepsort;

import java.util.Arrays;

/**
 * 堆排序
 * @author lynn
 * @date 2020/8/5 - 22:27
 */
public class HeapSort {
    public static void main(String[] args) {
        //调成大顶堆是升序的
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void heapSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            //交换
            int temp = arr[i];
            arr[i] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, i);
        }
    }

    private static void adjustHeap(int[] arr, int i, int length) {
        int tem = arr[i];
        //开始调整
        //说明
        //1. k=i*2 +1 是i节点的左子节点
        for (int k = i * 2 + 1; k < length; k = 2 * k + 1) {
            //说明左子节点小于右子节点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;//k指向右子节点
            }
            if (arr[k] > tem) {
                //交换
                arr[i] = arr[k];
                //注意 如果交换栈顶元素时 可能会破坏下面元素的结构 需要重新排序
                //指向k  继续循环比较；
                i = k;
            } else {
                break;//!
            }
        }
        //当for循环结束后，已经将以i为父节点的树的最大值放在了最顶上 只是局部
        //将temp放在调整后的位置
        arr[i] = tem;
    }
}
